package org.tonny.algorithm.leetcode;

import java.util.*;

/**
 * 239. 滑动窗口最大值
 */
public class LeetCode239 {
    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        LeetCode239 leetCode239 = new LeetCode239();
        System.out.println(Arrays.toString(leetCode239.maxSlidingWindow(nums, k)));
    }

    LinkedList<Integer> maxq = new LinkedList<>();

    public void push(int data) {
        //确保最大的数据在头结点处
        while (!maxq.isEmpty() && data > maxq.peekLast()) {
            maxq.pollLast();
        }
        maxq.offerLast(data);
    }

    public int max() {
        return maxq.peekFirst();
    }

    public void pop(int n) {
        if (!maxq.isEmpty() && maxq.peekFirst() == n) {
            maxq.pollFirst();
        }
    }

    /**
     * 看题解得到的答案
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            if (i < k - 1) {
                //先把前k-1个元素添加到队列中
                push(nums[i]);
                continue;
            }
            //增加滑动窗口右边的元素
            push(nums[i]);
            //取窗口的最大值，放入结果集中
            result[i - (k - 1)] = max();
            //去除滑动窗口左边的元素
            pop(nums[i - (k - 1)]);
        }
        return result;
    }

    /**
     * 大顶堆，超时
     */
    public int[] maxSlidingWindow2(int[] nums, int k) {
        //大顶堆，传入比较方法
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, (a, b) -> (b - a));

        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            if (i < k - 1) {
                //先把前k-1个元素添加到队列中
                queue.add(nums[i]);
                continue;
            }
            //增加滑动窗口右边的元素
            queue.offer(nums[i]);
            //取最大值
            result[i - (k - 1)] = queue.peek();
            //去除滑动窗口左边的元素
            queue.remove(nums[i - (k - 1)]);
        }
        return result;
    }


    /**
     * 暴力解法，超时
     */
    public int[] maxSlidingWindow1(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length - k + 1; i++) {
            //取窗口中的最大值
            result[i] = getMax(nums, i, k);
        }
        return result;
    }

    int getMax(int[] nums, int start, int k) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < k; i++) {
            max = Math.max(max, nums[start + i]);
        }
        return max;
    }
}